package com.leetcode.partition14;

import com.leetcode.common.TreeNode;

/**
 * @author rkc
 * @date 2022/9/8 9:53
 */
public class LC1373二叉搜索子树的最大键值和 {

    private static final int INF = (int) 1e8;
    private int ans = 0;

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int[] dfs(TreeNode u) {
        //(子树和，子树最小值，子树最大值)
        int[] l = new int[]{0, u.val, -INF}, r = new int[]{0, INF, u.val};
        if (u.left != null) l = dfs(u.left);
        if (u.right != null) r = dfs(u.right);
        if (l[2] < u.val && u.val < r[1]) {
            int s = l[0] + r[0] + u.val;
            ans = Math.max(ans, s);
            return new int[]{s, l[1], r[2]};
        }
        return new int[]{-INF, -INF, INF};
    }
}
